package uba.fi.tda.tp1.sorts;

public class QuickSort extends GenericSort {

	/**
	 * {@inheritDoc}
	 */
	@Override
	protected int[] sortMethod(int[] numbers) {		
		quicksort(numbers, 0, numbers.length - 1);
		return numbers;
	}

	/**
	 * Ordenamiento recursibo que separa el ordenamiento en dos mitades,
	 * 
	 * @param numbers
	 * @param indexLeft
	 * @param indexRight
	 */
	private void quicksort(int[] numbers, int indexLeft, int indexRight) {
		int lo = indexLeft;
		int hi = indexRight;

		if (lo >= hi) {
			return;
		} else if( lo == hi - 1 ) {
			if (numbers[lo] > numbers[hi]) {
				exchange(numbers, lo, hi);
			}
			return;
		}


		/*
		 *  Pick a pivot and move it out of the way
		 */
		int pivot = numbers[(lo + hi) / 2];
		numbers[(lo + hi) / 2] = numbers[hi];
		numbers[hi] = pivot;

		while( lo < hi ) {

			//Busqueda de numero desde inicio hasta que este sea mayor al pivot o el indice supere al superior.  
			while (numbers[lo] <= pivot && lo < hi) {
				lo++;
			}

			//Busqueda de numero por arriva hasta que el pivot sea menor o que el indice sea menor al indice low 
			while (pivot <= numbers[hi] && lo < hi ) {
				hi--;
			}

			//intercambio los numeros 
			if( lo < hi ) {
				exchange(numbers, lo, hi);
			}
		}

		//Coloco el medio 
		numbers[indexRight] = numbers[hi];
		numbers[hi] = pivot;

		//Llamada recursiva para las mitades entre los pivotes
		quicksort(numbers, indexLeft, lo-1);
		quicksort(numbers, hi+1, indexRight);
	}

	private void exchange(int[] a, int i, int j) {
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
}
